package problems.contest;

import java.util.Arrays;

/**
 * 力扣第106场双周赛
 * <p>https://leetcode.cn/contest/biweekly-contest-106/</p>
 *
 * @author dubulingbo, 2023/6/14 14:58.
 */
public class BCT106 {
    /**
     * T1|2729. 判断一个数是否迷人
     * <p>https://leetcode.cn/problems/check-if-the-number-is-fascinating/</p>
     */
    public boolean isFascinating(int n) {
        int[] cnt = new int[10];

        calc(n, cnt);
        calc(2 * n, cnt);
        calc(3 * n, cnt);

        for (int i = 1; i < 10; ++i) {
            if (cnt[i] != 1) return false;
        }

        return true;
    }

    private void calc(int n, int[] cnt) {
        while (n > 0) {
            ++cnt[n % 10];
            n /= 10;
        }
    }


    /**
     * T2|2730. 找到最长的半重复子字符串
     * <p>https://leetcode.cn/problems/find-the-longest-semi-repetitive-substring/</p>
     */
    public int longestSemiRepetitiveSubstring(String s) {
        int n = s.length();
        if (n < 3) return n;
        // 记录重复的位置下标
        int[] repeat = new int[n - 1];
        // 重复位置下标的数量
        int cnt = 0;

        for (int i = 0; i < n - 1; ++i) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                repeat[cnt++] = i;
            }
        }

        // 只有一个重复位置，直接返回原字符串的长度
        if (cnt < 2) return n;
        // 有 n-1 个重复位置，说明是相同字符串组成的字符串
        if (cnt == n - 1) return 2;

        // 当前的起始位置
        int pre = 0;
        int ans = 0;
        // 对重复位置进行枚举统计
        // 从第二个重复位置开始（允许有一个重复位置存在）
        for (int i = 1; i < cnt; ++i) {
            ans = Math.max(ans, repeat[i] - pre + 1);
            // 跳过前一个重复的位置
            pre = repeat[i - 1] + 1;
        }

        // 最后一段也要处理
        return Math.max(ans, n - pre);
    }


    /**
     * T3|2731. 移动机器人
     * <p>https://leetcode.cn/problems/movement-of-robots/</p>
     */
    public int sumDistance(int[] nums, String s, int d) {
        final long MOD = (long) 1e9 + 7;
        int n = nums.length;
        var a = new long[n];

        for (int i = 0; i < n; i++) // 注意 2e9+1e9 溢出了
            a[i] = (long) nums[i] + d * ((s.charAt(i) & 2) - 1); // L=-1, R=1

        long ans = 0, sum = 0;

        Arrays.sort(a);

        for (int i = 0; i < n; i++) {
            ans = (ans + i * a[i] - sum) % MOD;
            sum += a[i];
        }

        return (int) ans;
    }
}
